package sword.offer;

/**
 * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。
 * 要求时间复杂度是O(n)，空间复杂度是O(1)。
 * @author 胡宇轩
 * @Email: yuxuan.hu01@bianlifeng.com
 */
public class FiftySix {
    /**
     * 位运算类型题
     * 我们先从一个简单问题触发。从一组数中找出唯一一个出现次数为1的数，比如 6,6,7,7,8
     * 很显然，8就是我们要找的数。
     * 我们可以使用异或，来取到8。因为异或符合交换律 且 对同一个数进行异或 结果为0 ；而任何数 与 0进行异或等于其本身。
     * 故上题中，6和6进行异或后为0； 0和7进行异或为7；7和7进行异或为0；0和8进行异或为8.答案就是8.
     *
     * 本题在基于上题中 多了一个只出现一次的数。即 我们要找出两个仅出现一次的数。
     * 如：4,1,4,6。我们需要找出 1  和 6
     * 我们进行全员异或。 能够得出 1^6的结果 为 111
     * 就如上题中的方式，我们可以轻松找出1来。
     * 如果说能够将相同的数分在一组、不同的数分在不同的一组。那么这样是不是就很好找了呢？
     * 比如 4 4 1 为一组， 6为一组；
     * 因为4 和 4相同 他们分为一组；而 1 和 6 不同 则区分为一组。
     * 那么 从 4 4 1 中找出 1是不是很简单？  从 6中 找出 6 是不是很简单呢？
     *
     * 那么怎么分组呢？
     * 对于相同的数，不管它跟哪个数进行&运算，结果都一样。  那么 1 跟 6 呢？
     * 1 的 二进制为  0 0 0 1；  6 的二进制为 0 1 1 0； 我们发现两个数的最低位 就不一样。
     * 那我们只要分别对这两个数 将其 和 1进行&运算 就能够区分开来。
     * 所以我们只需要找到两个不同的数  的最低位的不同，就可以区分两个数了。
     *
     * 怎么找最低位不同的数？ 我们对1和6进行异或计算 ，得出结果111。1就表示 这个位置上的两位数不同。
     * 那么很显然 1 和 6最低位就不一样了。
     * */
    class Solution {
        public int[] singleNumbers(int[] nums) {
            int xor = 0;
            for (int n: nums) {
                xor ^= n;
            }
            // 找到最低位的不同的数
            int mask = 1;
            while((mask & xor) == 0){
                mask = mask << 1;
            }
            int a = 0;
            int b = 0;
            for (int n: nums) {
                if((n & mask) == 0){
                    a ^= n;
                }else{
                    b ^= n;
                }
            }
            return new int[]{a, b};
        }
    }
}
